class Solution:
    def maxSubArray(self, nums) -> int:
        pre_sum_min = 0
        pre_sum = 0
        max_ret = nums[0]
        for num in nums:
            pre_sum_min = min(pre_sum, pre_sum_min)
            pre_sum += num
            max_ret = max(pre_sum - pre_sum_min, max_ret)
        return max_ret


# nums = [-2,1,-3,4,-1,2,1,-5,4]
nums= [-2, -1]
nums = [-1,-2,-2,-2,3,2,-1,0]
tester = Solution()
print(tester.maxSubArray(nums))